package com.gjx.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

//101. 对称二叉树
//
//给定一个二叉树，检查它是否是镜像对称的。
//
//例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
//
//    1
//   / \
//  2   2
// / \ / \
//3  4 4  3
//但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
//
//    1
//   / \
//  2   2
//   \   \
//   3    3
//说明:
//
//如果你可以运用递归和迭代两种方法解决这个问题，会很加分。



public class Solution101 {
	public boolean isSymmetric(TreeNode root) {
        if (root == null) {
        	return true;
        }
        
        return helper(root.left, root.right);
    }
	
	
	private boolean helper(TreeNode left, TreeNode right) {
		if (left == null && right == null) {
			return true;
		} else if (left == null || right == null) {
			return false;
		} else if (left.val != right.val) {
			return false;
		}
		
		return helper(left.left, right.right) && helper(left.right, right.left);
	}
	
	
	public boolean isSymmetric2(TreeNode root) {
		if (root == null) {
			return true;
		}
		
		Queue<TreeNode> queue1 = new ArrayDeque<TreeNode>();
		Queue<TreeNode> queue2 = new ArrayDeque<TreeNode>();
		queue1.offer(root);
		queue2.offer(root);
		
		TreeNode empty = new TreeNode(0);
		
		while (!queue1.isEmpty() && !queue2.isEmpty()) {
			
			int size = queue1.size();
			
			for (int i=0; i<size; i++) {
				TreeNode t1 = queue1.poll();
				TreeNode t2 = queue2.poll();
				
				if (t1 == empty && t2 == empty) {
					continue;
				} else if (t1 == empty || t2 == empty) {
					return false;
				} else if (t1.val != t2.val){
					return false;
				} else {
					queue1.offer(t1.left == null ? empty : t1.left);
					queue1.offer(t1.right == null ? empty : t1.right);
					queue2.offer(t2.right == null ? empty : t2.right);
					queue2.offer(t2.left == null ? empty : t2.left);
				}
				
			}
			
		}
		
		return true;
		
	}
	
	public static void main(String[] args) {
		
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(2);
		
		new Solution101().isSymmetric2(root);
	}
	
}
